//给定一组唯一的单词， 找出所有不同 的索引对(i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。 
//
// 示例 1: 
//
// 输入: ["abcd","dcba","lls","s","sssll"]
//输出: [[0,1],[1,0],[3,2],[2,4]] 
//解释: 可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]
// 
//
// 示例 2: 
//
// 输入: ["bat","tab","cat"]
//输出: [[0,1],[1,0]] 
//解释: 可拼接成的回文串为 ["battab","tabbat"] 
// Related Topics 字典树 哈希表 字符串 
// 👍 79 👎 0

package leetcode.editor.cn;

import common.util.MyUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Java：回文对
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P336_PalindromePairs {
    public static void main(String[] args) {
        Solution solution = new P336_PalindromePairs().new Solution();
        String[] words = {"abcd","dcba","lls","s","sssll"};
        List<List<Integer>> res = solution.palindromePairs(words);
        MyUtil.print(res);
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 暴力, 会超时
     */
    class Solution {
        public List<List<Integer>> palindromePairs(String[] words) {
            List<List<Integer>> res = new ArrayList<>();
            if (words.length < 2) {
                return res;
            }
            for (int i = 0; i < words.length - 1; i++) {
                for (int j = i + 1; j < words.length; j++) {
                    if (isPalindrome(words[i] + words[j])) {
                        res.add(Arrays.asList(i, j));
                    }
                    if (isPalindrome(words[j] + words[i])) {
                        res.add(Arrays.asList(j, i));
                    }
                }
            }
            return res;
        }

        private boolean isPalindrome(String str) {
            return new StringBuilder(str).reverse().toString().equals(str);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
